"""
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，
找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。
如果不存在这样的转换序列，返回 0。

示例 1：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

链接：https://leetcode-cn.com/problems/word-ladder
"""
from mode import *


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if len(wordSet) == 0 or endWord not in wordSet:
            return 0
        if beginWord in wordSet:
            wordSet.remove(beginWord)

        deque = collections.deque()
        visited = set()
        steps = 1

        deque.append(beginWord)
        visited.add(beginWord)
        # beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
        while deque:

            for i in range(len(deque)):
                cur = deque.popleft()
                wordMyList = list(cur)

                for j in range(len(cur)):
                    originalChar = wordMyList[j]

                    for k in range(26):
                        wordMyList[j] = chr(ord('a') + k)
                        curWord = ''.join(wordMyList)
                        if curWord in wordSet:
                            if curWord == endWord:
                                return steps + 1
                            if curWord not in visited:
                                deque.append(curWord)
                                visited.add(curWord)

                    wordMyList[j] = originalChar
            steps += 1
        return 0


class Solution1:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if len(wordSet) == 0 or endWord not in wordSet:
            return 0
        if beginWord in wordSet:
            wordSet.remove(beginWord)

        deque = collections.deque()
        deque.append(beginWord)
        visited = set()
        visited.append(beginWord)
        step = 1
        while deque:
            # beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
            for i in range(len(deque)):
                curWord = deque.popleft()
                curWordList = list(curWord)
                for j in range(len(curWord)):
                    originalChar = curWordList[j]
                    for m in range(26):
                        curChar = chr(ord('a') + m)
                        curWordList[j] = curChar

                        tempWord = ''.join(curWordList)
                        if tempWord in wordSet:
                            print(tempWord)
                            if tempWord == endWord:
                                return step + 1
                            if tempWord not in visited:
                                visited.append(tempWord)
                                deque.append(tempWord)

                    curWordList[j] = originalChar
            step += 1
        return 0


if __name__ == "__main__":
    beginWord = "hit"
    endWord = "cog"
    wordList = ["hot", "dot", "dog", "lot", "log", "cog"]
    # "hit"
    # "cog"
    # ["hot","dot","dog","lot","log"]
    A = Solution()
    print(A.ladderLength(beginWord, endWord, wordList))
    A = Solution1()
    print(A.ladderLength(beginWord, endWord, wordList))
